Increasingly, inheritance hierarchies are being used to reduce redundancy innatural language processing lexicons. Systems that utilize inheritancehierarchies need to be able to insert words under the optimal set of classes inthese hierarchies. In this paper, we formalize this problem for feature-baseddefault inheritance hierarchies. Since the problem turns out to be NP-complete,we present an approximation algorithm for it. We show that this algorithm isefficient and that it performs well with respect to a number of standardproblems for default inheritance. A prototype implementation has been tested onlexical hierarchies and it has produced encouraging results. The work presentedhere is also relevant to other types of default hierarchies.
展开▼
